package datastructure;

import java.util.HashSet;
import java.util.Set;

/**
 * 重复数字
 * 找出数组中的重复数字
 *
 * @author miweidong
 * @date 2021-10-15 9:54
 */
public class RepeatNumber {
    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 0, 2, 5, 3, 5, 5};
        repeatNumber(arr);
        repeatNumber2(arr);
    }

    /**
     * 利用hash表找出重复数字
     *
     * @param arr 数组
     */
    public static void repeatNumber(int[] arr) {
        Set<Integer> numbers = new HashSet<>();
        Set<Integer> repeatNumber = new HashSet<>();
        for (int value : arr) {
            if (!numbers.add(value)) {
                repeatNumber.add(value);
            }
        }
        System.out.println(repeatNumber);
    }

    /**
     * hash表冲突找到重复数字
     * 我们认为，数组的索引就是数组中数的hash值，所以当索引和对应的值一致时，符合要求，如果索引处本身有值，再放的时候，会发生冲突
     *
     * @param arr 数组
     */
    public static void repeatNumber2(int[] arr) {
        Set<Integer> repeatNumber = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == i) {
                continue;
            }
            // 产生哈希冲突
            if (arr[arr[i]] == arr[i]) {
                repeatNumber.add(arr[i]);
            } else {
                int j = arr[i];
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        System.out.println(repeatNumber);
    }

}
